//
// Created by 党清浩 on 2021/10/23.
//
/**
 *      输入矩阵的行数、列数和非零元素个数，以及所有非零元素，非零元素包括每个元素的行号、列号、元素值。
 * 要求：①输入的非零元素个数必须满足稀疏矩阵要求，输入过程检测是否满足此要求，若不满足，则重新输入非零元素个数；
 *      ②非零元素按行号从小到大顺序输入，相同行号的元素，列号从小到大输入，输入过程检测是否满足此要求，
 *    若不满足，则重新输入当前非零元素的行号、列号和元素值
 */
#include <stdio.h>

#define MAXSIZE 100

typedef int ElemenType;

typedef struct {
    /* 非零元素的行下标 */
    int row;
    /* 非零元素的列下标 */
    int col;
    /* 该非零元素的值 */
    ElemenType e;
} Triple;

typedef struct {
    Triple data[MAXSIZE + 1];
    /* 矩阵的行数 */
    int m;
    /* 矩阵的列数 */
    int n;
    /* 矩阵的非零元素个数 */
    int len;
} TSMatrix;

/**
 *  稀疏矩阵输入
 */
void scanfTSMatrix(TSMatrix *A);

/**
 *  稀疏矩阵列序递增转置算法
 *  @param A 转置前
 *  @param B 转置后
 */
void TransposeTSMatrix(TSMatrix A, TSMatrix *B);

/**
 *  稀疏矩阵输出
 */
void printTSMatrix(TSMatrix B);

int main() {
    TSMatrix A;
    TSMatrix B;

    scanfTSMatrix(&A);

    printf("Before:\n");
    printTSMatrix(A);

    TransposeTSMatrix(A, &B);
    printf("After:\n");

    printTSMatrix(B);
    return 0;
}

/**
 * 稀疏矩阵输入
 * ①输入的非零元素个数必须满足稀疏矩阵要求，输入过程检测是否满足此要求，若不满足，则重新输入非零元素个数；
 * ②非零元素按行号从小到大顺序输入，相同行号的元素，列号从小到大输入，输入过程检测是否满足此要求，
 *   若不满足，则重新输入当前非零元素的行号、列号和元素值
 */
void scanfTSMatrix(TSMatrix *A) {
    /*输入行数，列数*/
    scanf("%d %d", &A->m, &A->n);
    do {
        /*输入非零元素个数，若不满足条件，重新输入*/
        scanf("%d", &A->len);
    } while (A->len > 0.3 * A->m * A->n);
    /*输入第一组行下标，列下标，元素值*/
    scanf("%d %d %d", &A->data[1].row, &A->data[1].col, &A->data[1].e);
    int s;
    for (s = 2; s <= A->len; s++) {
        do {
            /*输入剩余行下标，列下标，元素值，判断条件是否满足，否则重新输入*/
            scanf("%d %d %d", &A->data[s].row, &A->data[s].col, &A->data[s].e);
        } while (A->data[s].row < A->data[s - 1].row ||
                 A->data[s].row == A->data[s - 1].row &&
                 A->data[s].col <= A->data[s - 1].col);
    }
}

/**
 *  稀疏矩阵列序递增转置算法
 */
void TransposeTSMatrix(TSMatrix A, TSMatrix *B) {
    int i, j, k;
    /*B的行数等于A的列数*/
    B->m = A.n;
    /*B的列数等于A的行数*/
    B->n = A.m;
    /*B的非零元素个数等于A的非零元素个数*/
    B->len = A.len;

    if (B->len > 0) {
        /*j计数器，记录非零元素个数*/
        j = 1;
        /**/
        for (k = 1; k <= A.n; k++) {
            for (i = 1; i <= A.len; i++) {
                /* 从头到尾扫描三元组表A,寻找 col 值为 k 的三元组进行转置 */
                if (A.data[i].col == k) {
                    B->data[j].row = A.data[i].col;
                    B->data[j].col = A.data[i].row;
                    B->data[j].e = A.data[i].e;
                    j++;
                }
            }// for i end
        }// for k end
    }// if end
}// TransposeTSMatrix end

/**
 *  稀疏矩阵输出
 */
void printTSMatrix(TSMatrix B) {
    int i, j;
    /* k计数器，记录非零元素个数 */
    int k = 1;

    int zero = 0;
    for (i = 1; i <= B.m; i++) {
        for (j = 1; j <= B.n; j++) {
            /*得到行下标和列下表对应的位置输出非零元素的值，否则输出0*/
            if (B.data[k].row == i && B.data[k].col == j) {
                printf("%-4d", B.data[k].e);
                k++;
            } else {
                printf("%-4d", zero);
            }
        }
        printf("\n");
    }
}
